graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

, the bipartite double cover of an

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...

is a bipartite,

covering graph In the mathematical discipline of graph theory, a graph is a covering graph of another graph if there is a covering map from the vertex set of to the vertex set of . A covering map is a surjection and a local isomorphism: the neighbourhood of ...

of , with twice as many vertices as . It can be constructed as the

tensor product of graphs In graph theory, the tensor product of graphs and is a graph such that * the vertex set of is the Cartesian product ; and * vertices and are adjacent in if and only if ** is adjacent to in , and ** is adjacent to in . The tensor prod ...

, . It is also called the Kronecker double cover, canonical double cover or simply the bipartite double of . It should not be confused with a cycle double cover of a graph, a family of cycles that includes each edge twice.

Construction

The bipartite double cover of has two vertices and for each vertex of . Two vertices and are connected by an edge in the double cover if and only if and are connected by an edge in . For instance, below is an illustration of a bipartite double cover of a non-bipartite graph . In the illustration, each vertex in the tensor product is shown using a color from the first term of the product () and a shape from the second term of the product (); therefore, the vertices in the double cover are shown as circles while the vertices are shown as squares. : The bipartite double cover may also be constructed using adjacency matrices (as described below) or as the derived graph of a

voltage graph In graph theory, a voltage graph is a directed graph whose edges are labelled invertibly by elements of a group. It is formally identical to a gain graph, but it is generally used in topological graph theory as a concise way to specify another gra ...

in which each edge of is labeled by the nonzero element of the two-element

group A group is a number of persons or things that are located, gathered, or classed together. Groups of people * Cultural group, a group whose members share the same cultural identity * Ethnic group, a group whose members share the same ethnic iden ...

Examples

The bipartite double cover of the

Petersen graph In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is n ...

is the

Desargues graph In the mathematical field of graph theory, the Desargues graph is a distance-transitive, cubic graph with 20 vertices and 30 edges. It is named after Girard Desargues, arises from several different combinatorial constructions, has a high level ...

: . The bipartite double cover of a

complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is c ...

is a

crown graph In graph theory, a branch of mathematics, a crown graph on vertices is an undirected graph with two sets of vertices and and with an edge from to whenever . The crown graph can be viewed as a complete bipartite graph from which the edges ...

complete bipartite graph In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17. Graph theory ...

minus a

perfect matching In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph , a perfect matching in is a subset of edge set , such that every vertex in the vertex set is adjacent to exactly ...

). In particular, the bipartite double cover of the graph of a

tetrahedron In geometry, a tetrahedron (plural: tetrahedra or tetrahedrons), also known as a triangular pyramid, is a polyhedron composed of four triangular faces, six straight edges, and four vertex corners. The tetrahedron is the simplest of all the o ...

, , is the graph of a

cube In geometry, a cube is a three-dimensional solid object bounded by six square faces, facets or sides, with three meeting at each vertex. Viewed from a corner it is a hexagon and its net is usually depicted as a cross. The cube is the only r ...

. The bipartite double cover of an odd-length

cycle graph In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices (at least 3, if the graph is simple) connected in a closed chain. The cycle graph with vertices is called ...

is a cycle of twice the length, while the bipartite double of any bipartite graph (such as an even length cycle, shown in the following example) is formed by two disjoint copies of the original graph. :

Matrix interpretation

If an undirected graph has a matrix as its

adjacency matrix In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. In the special case of a finite simp ...

, then the adjacency matrix of the double cover of is :

\left begin0&A\\A^T&0\end\right

and the

biadjacency matrix In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. In the special case of a finite simpl ...

of the double cover of is just itself. That is, the conversion from a graph to its double cover can be performed simply by reinterpreting as a biadjacency matrix instead of as an adjacency matrix. More generally, the reinterpretation the adjacency matrices of

directed graph In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. Definition In formal terms, a directed graph is an ordered pa ...

s as biadjacency matrices provides a combinatorial equivalence between directed graphs and balanced bipartite graphs.

Properties

The bipartite double cover of any graph is a

bipartite graph In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V are ...

; both parts of the bipartite graph have one vertex for each vertex of . A bipartite double cover is

connected Connected may refer to: Film and television * ''Connected'' (2008 film), a Hong Kong remake of the American movie ''Cellular'' * '' Connected: An Autoblogography About Love, Death & Technology'', a 2011 documentary film * ''Connected'' (2015 TV ...

if and only if is connected and non-bipartite. The bipartite double cover is a special case of a ''double cover'' (a 2-fold

). A double cover in graph theory can be viewed as a special case of a topological double cover. If is a non-bipartite

symmetric graph In the mathematical field of graph theory, a graph is symmetric (or arc-transitive) if, given any two pairs of adjacent vertices and of , there is an automorphism :f : V(G) \rightarrow V(G) such that :f(u_1) = u_2 and f(v_1) = v_2. In oth ...

, the double cover of is also a symmetric graph; several known cubic symmetric graphs may be obtained in this way. For instance, the double cover of is the graph of a cube; the double cover of the Petersen graph is the Desargues graph; and the double cover of the graph of the

dodecahedron In geometry, a dodecahedron (Greek , from ''dōdeka'' "twelve" + ''hédra'' "base", "seat" or "face") or duodecahedron is any polyhedron with twelve flat faces. The most familiar dodecahedron is the regular dodecahedron with regular pentagon ...

is a 40-vertex symmetric cubic graph. It is possible for two different graphs to have

isomorphic In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word is ...

bipartite double covers. For instance, the Desargues graph is not only the bipartite double cover of the Petersen graph, but is also the bipartite double cover of a different graph that is not isomorphic to the Petersen graph.. Not every bipartite graph is a bipartite double cover of another graph; for a bipartite graph to be the bipartite cover of another graph, it is necessary and sufficient that the

automorphism In mathematics, an automorphism is an isomorphism from a mathematical object to itself. It is, in some sense, a symmetry of the object, and a way of mapping the object to itself while preserving all of its structure. The set of all automorphisms ...

s of include an

involution Involution may refer to: * Involute, a construction in the differential geometry of curves * '' Agricultural Involution: The Processes of Ecological Change in Indonesia'', a 1963 study of intensification of production through increased labour inpu ...

that maps each vertex to a distinct and non-adjacent vertex. For instance, the graph with two vertices and one edge is bipartite but is not a bipartite double cover, because it has no non-adjacent pairs of vertices to be mapped to each other by such an involution; on the other hand, the graph of the cube is a bipartite double cover, and has an involution that maps each vertex to the diametrally opposite vertex. An alternative characterization of the bipartite graphs that may be formed by the bipartite double cover construction was obtained by .

Name

In a

connected graph In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to separate the remaining nodes into two or more isolated subgrap ...

that is not bipartite, only one double cover is bipartite, but when the graph is bipartite or disconnected there may be more than one. For this reason,

Tomaž Pisanski Tomaž (Tomo) Pisanski (born 24 May 1949 in Ljubljana, Yugoslavia, which is now in Slovenia) is a Slovenian mathematician working mainly in discrete mathematics and graph theory. He is considered by many Slovenian mathematicians to be the "father ...

has argued that the name "bipartite double cover" should be deprecated in favor of the "canonical double cover" or "Kronecker cover", names which are unambiguous.

Other double covers

In general, a graph may have multiple double covers that are different from the bipartite double cover.. # The graph is a ''covering graph'' of if there is a surjective local isomorphism from to . In the figure, the surjection is indicated by the colours. For example, maps both blue nodes in to the blue node in . Furthermore, let be the

neighbourhood A neighbourhood (British English, Irish English, Australian English and Canadian English) or neighborhood (American English; see spelling differences) is a geographically localised community within a larger city, town, suburb or rural are ...

of a blue node in and let be the neighbourhood of the blue node in ; then the restriction of to is a

bijection In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other s ...

from to . In particular, the degree of each blue node is the same. The same applies to each colour. # The graph is a ''double cover'' (or ''2-fold cover'' or ''2-lift'') of if the preimage of each node in has size 2. In the example, there are exactly 2 nodes in that are mapped to the blue node in . In the following figure, the graph is a double cover of the graph : : However, is not the ''bipartite double cover'' of or any other graph; it is not a bipartite graph. If we replace one triangle by a square in the resulting graph has four distinct double covers. Two of them are bipartite but only one of them is the Kronecker cover. As another example, the graph of the

icosahedron In geometry, an icosahedron ( or ) is a polyhedron with 20 faces. The name comes and . The plural can be either "icosahedra" () or "icosahedrons". There are infinitely many non- similar shapes of icosahedra, some of them being more symmetrica ...

is a double cover of the complete graph ; to obtain a covering map from the icosahedron to , map each pair of opposite vertices of the icosahedron to a single vertex of . However, the icosahedron is not bipartite, so it is not the bipartite double cover of . Instead, it can be obtained as the

orientable double cover In mathematics, orientability is a property of some topological spaces such as real vector spaces, Euclidean spaces, Surface (topology), surfaces, and more generally manifolds that allows a consistent definition of "clockwise" and "counterclo ...

of an

embedding In mathematics, an embedding (or imbedding) is one instance of some mathematical structure contained within another instance, such as a group that is a subgroup. When some object X is said to be embedded in another object Y, the embedding is gi ...

of on the

projective plane In mathematics, a projective plane is a geometric structure that extends the concept of a plane. In the ordinary Euclidean plane, two lines typically intersect in a single point, but there are some pairs of lines (namely, parallel lines) that do ...

. The double covers of a graph correspond to the different ways to sign the edges of the graph.

Notes

References

*. *. The “coverings” in the title of this paper refer to the

vertex cover In graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices that includes at least one endpoint of every edge of the graph. In computer science, the problem of finding a minimum vertex cover is a classical optimizat ...

problem, not to bipartite double covers. However, cite this paper as the source of the idea of reinterpreting the adjacency matrix as a biadjacency matrix. *. *. * *. *.

External links

*{{mathworld , title = Bipartite Double Graph , urlname = BipartiteDoubleGraph Graph operations Bipartite graphs